package com.lw.leetcode.sort.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 948. 令牌放置
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/24 16:49
 */
public class BagOfTokensScore {

    public static void main(String[] args) {
        BagOfTokensScore test = new BagOfTokensScore();

        // 0
        int[] arr = {100};
        int p = 50;

        // 1
//        int[] arr = {100,200};
//        int p = 150;

        // 2
//        int[] arr = {100,200,300,400};
//        int p = 200;

        int i = test.bagOfTokensScore(arr, p);
        System.out.println(i);
    }

    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int length = tokens.length - 1;
        int max = 0;
        int item = 0;
        for (int i = 0; i <= length; i++) {
            int t = tokens[i];
            if (t <= power) {
                power -= t;
                item++;
                max = Math.max(max, item);
            } else {
                item--;
                power += tokens[length--];
                if (item < 0) {
                    return max;
                }
                i--;
            }
        }
        return max;
    }
}
